package week09

// 127. 单词接龙
// https://leetcode-cn.com/problems/word-ladder/

func ladderLength(beginWord string, endWord string, wordList []string) int {
	var distBegin = make(map[string]int, len(wordList))
	var distEnd = make(map[string]int, len(wordList))
	for _, word := range wordList {
		distBegin[word] = 1e9
		distEnd[word] = 1e9
	}
	if _, ok := distBegin[endWord]; !ok {
		return 0
	}
	distBegin[beginWord], distEnd[endWord] = 1, 1

	var qBegin, qEnd = []string{beginWord}, []string{endWord}
	var ans = 0
	for len(qBegin) > 0 && len(qEnd) > 0 {
		if qBegin, ans = bfs(qBegin, distBegin, distEnd); ans > 0 {
			return ans
		}
		if qEnd, ans = bfs(qEnd, distEnd, distBegin); ans > 0 {
			return ans
		}
	}
	return 0
}

func bfs(queue []string, dist, other map[string]int) ([]string, int) {
	top := queue[0]
	queue = queue[1:]

	depth := dist[top]
	bytes := []byte(top)
	for i := range bytes {
		for k := byte('a'); k <= 'z'; k++ {
			backup := bytes[i]
			bytes[i] = k
			s := string(bytes)
			if d, ok := dist[s]; ok && d > depth+1 {
				dist[s] = depth + 1
				if v, ok := other[s]; ok && v != 1e9 {
					return nil, depth + other[s]
				}
				queue = append(queue, s)
			}
			bytes[i] = backup
		}
	}
	return queue, 0
}